import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:龙宝
 * Date:2023-11-12
 * Time:16:51
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {9,4,1,2,0,6,5,3,10,7,8};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void heapSort(int[] arr) {
        //构建二叉树
        createTreeNode(arr,0,arr.length);

        //将二叉树的根放在已排序的最前面，倒着放
        for(int i = arr.length-1;i>0;i--) {
            int tmp = arr[0];
            arr[0] = arr[i];
            arr[i] = tmp;
            createTreeNode(arr,0,i);
        }
    }

    private static void createTreeNode(int[] arr, int start, int len) {
        for(int k = len/2-1;k>=0;k--) {
            int i = 2*k +1;
            if(i+1<len && arr[i] < arr[i+1]) {
                i++;
            }
            if(arr[i] > arr[k]) {
                int tmp = arr[i];
                arr[i] = arr[k];
                arr[k] = tmp;
            }
        }
    }
}
